#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sys/time.h>

using namespace std;

struct TreeNode
{
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };


TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
{
  TreeNode * ret = new TreeNode(0);
  if(inorder.size()==0)
  {
    return NULL;
  }
  if(inorder.size()==1)
  {
    ret->val = inorder.at(0);
    return ret;
  }

  int r;
  r = postorder.back();
  ret->val = r;

  vector<int>::iterator r_iter = std::find( inorder.begin(), inorder.end(), r );
  int r_index = r_iter - inorder.begin();

  vector<int> in_lc( inorder.begin(), r_iter );
  vector<int> in_rc( r_iter+1, inorder.end() );

  vector<int> po_lc( postorder.begin(), postorder.begin()+r_index );
  vector<int> po_rc( postorder.begin()+r_index, postorder.end()-1 );

  inorder.clear();
  inorder.shrink_to_fit();
  postorder.clear();
  postorder.shrink_to_fit();

  ret->left = buildTree( in_lc, po_lc );
  ret->right = buildTree( in_rc, po_rc );

  return ret;


   
}



int main(int argc,char *argv[])
{
  vector<int> inorder = {4,2,5,1,6,3,7};
  vector<int> postorder = {4,5,2,6,7,3,1};

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  TreeNode * root  = buildTree(inorder,postorder);

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

 



  return 0;
}
